/**
 *  @file LinklistCircleQueue.c
 *  @desc 基于带头结点的单向循环链表实现队列（链式循环队列）
 *        支持：初始化、入队、出队、查看队头、判空、长度、打印、清空等基本操作。
 *        设计要点：
 *          - 使用一个**头节点（哨兵）**，head->next 指向第一个有效节点；当队列为空时，头节点的 next 指向自身。
 *          - front 指向头节点，rear 指向队尾节点；空队列时 front == rear。
 *  @author WangBlue (wangjiping596@gmail.com)
 *  @date 2025-07-29 16:38
 *  @version 1.0
 */

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>

/* ========================== 类型定义 ========================== */

/**
 * @brief 队列节点（单向）
 */
typedef struct node {
    int data;              ///< 节点存储的数据
    struct node *next;     ///< 指向下一个节点
} node;

/**
 * @brief 循环链队列封装（保存头、尾指针）
 *
 * - front: 指向头节点（哨兵）；head->next 指向第一个有效节点（或指向自身表示空）
 * - rear : 指向尾节点；空队列时 rear == front
 */
typedef struct circleQueue {
    node *front;
    node *rear;
} circleQueue;

/* ========================== 辅助函数 ========================== */

/**
 * @brief 创建并初始化一个新节点
 * @param value 节点要保存的整数值
 * @return 成功返回指向新节点的指针；失败返回 NULL
 * @complexity O(1)
 */
node* createNode(int value) {
    node *newNode = (node *) malloc(sizeof(node));
    if (newNode == NULL) return NULL;
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

/* ========================== 队列基本操作 ========================== */

/**
 * @brief 初始化循环链队列（创建头节点并构成自环）
 * @param q 指向要初始化的 circleQueue 结构体
 * @note 若内存分配失败，当前实现打印错误并退出程序（可按需修改为返回错误码）。
 * @complexity O(1)
 */
void initCircleQueue(circleQueue *q) {
    node *newNode = createNode(0);    // 头节点，data 字段可作占位
    if (!newNode) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    newNode->next = newNode;          // 自环：head->next 指向自己，表示空队列

    q->front = q->rear = newNode;     // front 和 rear 初始都指向头节点
}

/**
 * @brief 判断队列是否为空
 * @param q 指向循环队列
 * @return true 表示为空，false 表示非空
 * @complexity O(1)
 */
bool isEmpty(circleQueue *q) {
    return q->front == q->rear;
}

/**
 * @brief 入队：在队尾插入一个新节点
 * @param q 指向循环队列
 * @param value 要入队的整数值
 * @note
 *   - 新节点的 next 应指向头节点（保持循环结构）。
 *   - 本实现对 createNode 返回值进行了空检查并在失败时退出；在库函数中可改成返回错误码以便调用者处理。
 * @complexity O(1)
 */
void inQueue(circleQueue *q, int value) {
    node *newNode = createNode(value);
    if (newNode == NULL) {
        /* 更健壮的实现应向上抛出错误或返回状态码，这里直接退出以保持简单 */
        printf("Memory allocation failed in inQueue().\n");
        exit(1);
    }

    // 新节点的 next 指向头节点（队列循环性质）
    newNode->next = q->front;

    // 原尾节点的 next 指向新节点，更新尾指针
    q->rear->next = newNode;
    q->rear = newNode;
}

/**
 * @brief 出队：移除并返回队头元素（第一个有效节点）
 * @param q 指向循环队列
 * @param value 指针，用于保存出队的元素值（若队列为空，不写入）
 * @note
 *   - 若队列为空，函数直接返回（不修改 *value）；更好的接口应返回 bool 表示成功/失败。
 *   - **注意：原始实现中有一个明显的 bug：在删除最后一个元素时，代码使用 `q->front = q->rear;`
 *     这会把 front 指针指向已释放节点，从而导致悬挂指针。正确的处理应是把 rear 回退到头节点：`q->rear = q->front;`。**
 * @complexity O(1)
 */
void deQueue(circleQueue *q, int *value) {
    if (isEmpty(q)) return;               // 空队列无操作

    node *temp = q->front->next;          // 第一个有效节点
    *value = temp->data;                  // 提取数据

    // 断开第一个节点并连接到下一个
    q->front->next = temp->next;

    // 若被删除的是尾节点（队列只有一个元素），需要将 rear 回退到头节点
    if (temp == q->rear) {
        /* 修复：应设置 rear = front，而不是 front = rear（后者会破坏 head 指针并指向已释放内存） */
        q->rear = q->front;
    }

    free(temp);                           // 释放节点内存
}

/**
 * @brief 查看队头元素但不出队
 * @param q 指向循环队列
 * @param value 指针，用于保存队头元素值（若队列为空，不写入）
 * @note 建议把函数改为返回 bool 表示是否成功读取队头，以便调用者区分空队列情况。
 * @complexity O(1)
 */
void peek(circleQueue* q, int* value) {
    if (isEmpty(q)) return;
    *value = q->front->next->data;
}

/**
 * @brief 顺序打印队列中所有元素（从队头到队尾）
 * @param q 指向循环队列
 * @complexity O(n)
 */
void printQueue(circleQueue *q) {
    if (isEmpty(q)) return;

    node *cur = q->front->next;           // 从第一个有效节点开始
    while (cur != q->front) {             // 遍历直到回到头节点
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * @brief 获取队列中元素个数
 * @param q 指向循环队列
 * @return 队列中有效元素的数量（空队列返回 0）
 * @complexity O(n)
 */
int getLength(circleQueue *q) {
    int length = 0;
    if (isEmpty(q)) return length;

    node *cur = q->front->next;
    while (cur != q->front) {
        cur = cur->next;
        length++;
    }
    return length;
}

/**
 * @brief 清空队列：释放所有数据节点，保留头节点并将队列恢复为空
 * @param q 指向循环队列
 * @note 清空后 q->rear = q->front，q->front->next 指向自身
 * @complexity O(n)
 */
void clearQueue(circleQueue *q) {
    if (isEmpty(q)) return;

    node *cur = q->front->next;
    while (cur != q->front) {
        node *temp = cur;
        cur = temp->next;
        free(temp);
    }

    // 恢复为空队列的状态
    q->rear = q->front;
    q->front->next = q->front;
}

/* ========================== 测试主函数 ========================== */

int main() {
    circleQueue q;
    initCircleQueue(&q);

    inQueue(&q, 1);
    inQueue(&q, 2);
    inQueue(&q, 3);
    inQueue(&q, 4);

    int val;
    peek(&q, &val);
    printf("peek: %d\n", val);    // 期望输出队头元素 1

    printQueue(&q);               // 打印全部元素：1 2 3 4

    deQueue(&q, &val);
    printf("dequeue: %d\n", val); // 期望输出 1

    printQueue(&q);               // 打印剩余元素：2 3 4

    printf("length is %d\n", getLength(&q)); // 输出长度 3

    clearQueue(&q);               // 清空队列（释放数据节点）
    return 0;
}
